package four.sum.count.is.zero;

import java.util.HashMap;
import java.util.Map;

/**
 * @Time 2020/1/3
 * @author 王光浩
 * @Need 给出四个整型的list，找出所有可能的的数据组，数据组需要满足相加之和为0，并且数据中只能有四个元素
 * 		 分别来自于四个list。
 * @Thinking 使用HashMap+暴力法。
 *           思路：创建两个HashMap，key值为累加和，value为出现次数。使用两个双层循环，将四个List分成两组
 *                 ，将每两组的所有可能累加和存放在HashMap中，然后使用一个一层循环，统计组数。
 *           复杂度分析：时间复杂度O（n^2）,空间复杂度O（4n），n为list长度
 *           
 *           改进：使用一个HashMap来解决该问题。
 */
public class MyMethodThree {
    public int fourSumCount1(int[] A, int[] B, int[] C, int[] D) {
    	Map<Integer,Integer> group1=new HashMap<Integer,Integer>();
    	Map<Integer,Integer> group2=new HashMap<Integer,Integer>();
    	int count=0;
    	//将A、B所有0-累加和存放在group1中，并记录出现次数
    	for(int i:A) {
    		for(int j:B) {
    			group1.put(-i-j, group1.getOrDefault(-i-j, 0)+1);
    		}
    	}
    	//将C、D所有累加和存放在group2中，并记录出现次数
    	for(int i:C) {
    		for(int j:D) {
    			group2.put(i+j, group2.getOrDefault(i+j, 0)+1);
    		}
    	}
    	//找出符合要求的数据组
    	for(Map.Entry<Integer,Integer> entry :  group1.entrySet())  {
    		if(group2.containsKey(entry.getKey()))
    			count+=(entry.getValue()*group2.get(entry.getKey()));
    	}
    	return count;
    }
    
    //改进后的代码
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
    	Map<Integer,Integer> group=new HashMap<Integer,Integer>();
    	int count=0;
    	//将A、B所有0-累加和存放在group中，并记录出现次数
    	for(int i:A) {
    		for(int j:B) {
    			group.put(-i-j, group.getOrDefault(-i-j, 0)+1);
    		}
    	}
    	//统计组数
    	for(int i:C) {
    		for(int j:D) {
    			if(group.containsKey(i+j))
    				count+=group.get(i+j);
    		}
    	}
    	return count;
    }

}
